// Copyright (c) 2005-2008, Simon Howard
// Permission to use, copy, modify, and/or distribute this software
// for any purpose with or without fee is hereby granted, provided
// that the above copyright notice and this permission notice appear
// in all copies.
// THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL
// WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED
// WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE
// AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT, INDIRECT, OR
// CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
// LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT,
// NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
// CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.

use std::fmt::Debug;

/// A trait representing a hash function that can be used with the Bloom filter.
pub trait HashFunction: Debug {
    fn hash(&self, data: &str) -> u64;
}

/// A struct representing a Bloom filter.
pub struct BloomFilter<H: HashFunction> {
    buffer: Vec<bool>,
    hash_function: H,
    num_salts: usize,
}

impl<H: HashFunction> BloomFilter<H> {
    /// Creates a new Bloom filter with the specified buffer size, hash function, and number of salts.
    pub fn new(buffer_size: usize, hash_function: H, num_salts: usize) -> Option<Self> {
        if num_salts > 64 {
            return None;
        }
        Some(Self {
            buffer: vec![false; buffer_size],
            hash_function,
            num_salts,
        })
    }

    /// Inserts a value into the Bloom filter.
    pub fn insert(&mut self, value: &str) {
        let hash = self.hash_function.hash(value);
        for i in 0..self.num_salts {
            let index = (hash as usize + i) % self.buffer.len();
            self.buffer[index] = true;
        }
    }

    /// Queries the Bloom filter to check if a value might be present.
    pub fn query(&self, value: &str) -> bool {
        let hash = self.hash_function.hash(value);
        for i in 0..self.num_salts {
            let index = (hash as usize + i) % self.buffer.len();
            if !self.buffer[index] {
                return false;
            }
        }
        true
    }

    /// Reads the current state of the Bloom filter into a byte array.
    pub fn read(&self, state: &mut [u8]) {
        let bytes_per_bool = std::mem::size_of::<bool>();
        for (i, &bit) in self.buffer.iter().enumerate() {
            let byte_index = i / (8 / bytes_per_bool);
            let bit_index = i % (8 / bytes_per_bool);
            state[byte_index] |= (bit as u8) << bit_index;
        }
    }

    /// Loads the state of the Bloom filter from a byte array.
    pub fn load(&mut self, state: &[u8]) {
        let bytes_per_bool = std::mem::size_of::<bool>();
        for (i, bit) in self.buffer.iter_mut().enumerate() {
            let byte_index = i / (8 / bytes_per_bool);
            let bit_index = i % (8 / bytes_per_bool);
            *bit = (state[byte_index] & (1 << bit_index)) != 0;
        }
    }

    /// Computes the intersection of two Bloom filters.
    pub fn intersection(&self, other: &Self) -> Option<Self> {
        if self.buffer.len() != other.buffer.len() || self.num_salts != other.num_salts {
            return None;
        }
        let mut new_buffer = self.buffer.clone();
        for (a, b) in new_buffer.iter_mut().zip(other.buffer.iter()) {
            *a &= *b;
        }
        Some(Self {
            buffer: new_buffer,
            hash_function: self.hash_function.clone(),
            num_salts: self.num_salts,
        })
    }

    /// Computes the union of two Bloom filters.
    pub fn union(&self, other: &Self) -> Option<Self> {
        if self.buffer.len() != other.buffer.len() || self.num_salts != other.num_salts {
            return None;
        }
        let mut new_buffer = self.buffer.clone();
        for (a, b) in new_buffer.iter_mut().zip(other.buffer.iter()) {
            *a |= *b;
        }
        Some(Self {
            buffer: new_buffer,
            hash_function: self.hash_function.clone(),
            num_salts: self.num_salts,
        })
    }
}

#[derive(Debug, Clone)]
struct StringHash;

impl HashFunction for StringHash {
    fn hash(&self, data: &str) -> u64 {
        // Dummy hash function for demonstration purposes
        data.len() as u64
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_bloom_filter_new_free() {
        let filter = BloomFilter::new(128, StringHash, 1);
        assert!(filter.is_some());
        let filter = BloomFilter::new(128, StringHash, 64);
        assert!(filter.is_some());
        let filter = BloomFilter::new(128, StringHash, 50000);
        assert!(filter.is_none());
    }

    #[test]
    fn test_bloom_filter_insert_query() {
        let mut filter = BloomFilter::new(128, StringHash, 4).unwrap();
        assert!(!filter.query("test 1"));
        assert!(!filter.query("test 2"));
        filter.insert("test 1");
        filter.insert("test 2");
        assert!(filter.query("test 1"));
        assert!(filter.query("test 2"));
    }

    #[test]
    fn test_bloom_filter_read_load() {
        let mut filter1 = BloomFilter::new(128, StringHash, 4).unwrap();
        filter1.insert("test 1");
        filter1.insert("test 2");
        let mut state = [0u8; 16];
        filter1.read(&mut state);
        let mut filter2 = BloomFilter::new(128, StringHash, 4).unwrap();
        filter2.load(&state);
        assert!(filter2.query("test 1"));
        assert!(filter2.query("test 2"));
    }

    #[test]
    fn test_bloom_filter_intersection() {
        let mut filter1 = BloomFilter::new(128, StringHash, 4).unwrap();
        filter1.insert("test 1");
        filter1.insert("test 2");
        let mut filter2 = BloomFilter::new(128, StringHash, 4).unwrap();
        filter2.insert("test 1");
        assert!(!filter2.query("test 2"));
        let result = filter1.intersection(&filter2);
        assert!(result.is_some());
        let result = result.unwrap();
        assert!(result.query("test 1"));
        assert!(!result.query("test 2"));
    }

    #[test]
    fn test_bloom_filter_union() {
        let mut filter1 = BloomFilter::new(128, StringHash, 4).unwrap();
        filter1.insert("test 1");
        let mut filter2 = BloomFilter::new(128, StringHash, 4).unwrap();
        filter2.insert("test 2");
        let result = filter1.union(&filter2);
        assert!(result.is_some());
        let result = result.unwrap();
        assert!(result.query("test 1"));
        assert!(result.query("test 2"));
    }

    #[test]
    fn test_bloom_filter_mismatch() {
        let filter1 = BloomFilter::new(128, StringHash, 4).unwrap();
        let filter2 = BloomFilter::new(64, StringHash, 4).unwrap();
        assert!(filter1.intersection(&filter2).is_none());
        assert!(filter1.union(&filter2).is_none());
        let filter2 = BloomFilter::new(128, StringHash, 32).unwrap();
        assert!(filter1.intersection(&filter2).is_none());
        assert!(filter1.union(&filter2).is_none());
    }
}
